package leetcode;

import java.util.*;

/**
 * 128. 最长连续序列
 * 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
 *
 * 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [100,4,200,1,3,2]
 * 输出：4
 * 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
 * 示例 2：
 *
 * 输入：nums = [0,3,7,2,5,8,4,6,0,1]
 * 输出：9
 *
 */
public class LongestConsecutive {

    public static void main(String[] args) {
        int[] arr = {100, 4, 200, 1, 3, 2};

        int ans = longestConsecutive(arr);
        System.out.println(ans);

    }
    /**
     * contains
     *
     * 奇技淫巧的典范
     *
     * @param nums
     * @return
     */
    public static int longestConsecutive(int[] nums) {
            if (nums == null || nums.length == 0) {
                return 0;
            }
            int max = 1;
            Set<Integer> set = new HashSet();
            for (int i : nums) {
                set.add(i);
            }

            for (int i : set) {
                int tempMax = 1;
                int curValue = i;
                if (set.contains(curValue - 1)) {
                    continue;
                }

                while (set.contains(curValue+1)){
                    tempMax++;
                    curValue++;
                }
                max = Math.max(max, tempMax);
            }

            return max;

    }
}
